package 题目集.单调栈or队列.单调队列.舍弃可能性;

import org.junit.Test;

/**
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
 * https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/description/
 */
public class 搭配前缀和 {
    /**
     * 暴力的前缀和思路：
     *      枚举每个起点，枚举该起点的所有终点，找到和>=K的最小长度
     *      时间复杂度：O(n^2)
     */
    public int shortestSubarray1(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= k) {
                    res = Math.min(res, j - i + 1);
                    break;
                }
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    @Test
    public void test() {
        System.out.println(shortestSubarray1(new int[]{2, -1, 2}, 3));
    }

    /**
     * 如果理解不了，推荐先看{@link 题目集.前缀和.最大子数组和}的解法
     * 我们可以将题目分析为：已知数组前缀和，求 s[r]-s[l-1]>=k时，r-l的最小值。
     *      那么s[l-1]一定满足这样的要求：
     *          s[l-1]<s[l]，也就是说当s[l-1]>s[l]时，就没有必要讨论了。（r-l比r-(l-1)短，而且s[r]-s[l]比s[r]-s[l-1]大）
     *      所以我们可以维护一个单调递增的队列，队列中存储的是前缀和的下标。
     *      当s[r]-s[l-1]满足要求时，记录答案，并尝试求s[r]-s[l]是否满足要求。
     */
    public int shortestSubarray(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        long[] sum = new long[nums.length + 1];
        int[] queue = new int[nums.length + 1];
        int n = nums.length;
        int head = 0, tail = 0;
        for (int i = 1; i <=n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        for (int j = 0; j <=n; j++) {
            while (head != tail && sum[j] < sum[queue[tail - 1]]) { //舍弃左侧比自己大的情况
                tail--;
            }
            queue[tail++] = j;  //添加当前数,保证队列是递增的
            while (head != tail && sum[j] - sum[queue[head]] >= k) {    //如果当前数满足条件，尝试舍弃头部的数
                res = Math.min(res, j - queue[head++]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    @Test
    public void test2() {
        System.out.println(shortestSubarray(new int[]{-100, -100, -100}, 20));
    }

}
